DROPS

Document

DOI: 10.4230/LIPIcs.CALCO.2021.20

The Open Algebraic Path Problem

Authors: Jade Master

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract

The algebraic path problem provides a general setting for shortest path algorithms in optimization and computer science. We explain the universal property of solutions to the algebraic path problem by constructing a left adjoint functor whose values are given by these solutions. This paper extends the algebraic path problem to networks equipped with input and output boundaries. We show that the algebraic path problem is functorial as a mapping from a double category whose horizontal composition is gluing of open networks. We introduce functional open matrices, for which the functoriality of the algebraic path problem has a more practical expression.

Cite as

Jade Master. The Open Algebraic Path Problem. In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{master:LIPIcs.CALCO.2021.20,
  author =	{Master, Jade},
  title =	{{The Open Algebraic Path Problem}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.20},
  URN =		{urn:nbn:de:0030-drops-153754},
  doi =		{10.4230/LIPIcs.CALCO.2021.20},
  annote =	{Keywords: The Algebraic Path Problem, Open Systems, Shortest Paths, Categorical Semantics, Compositionality}
}

Search Results

Documents authored by Master, Jade

The Open Algebraic Path Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message